#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct Node {
	int data;
	struct Node *next;
} Node;

// 尾插法
void insert_tail(Node **head, int val) {
	Node *new_node = calloc(1, sizeof(Node));	// 用calloc避免忘记设置next域为NULL
	if (new_node == NULL) {
		printf("malloc failed in insert_tail.\n");
		exit(1);
	}
	new_node->data = val;
	if (*head == NULL) {
		*head = new_node;
	}
	else {
		Node *curr = *head;
		while (curr->next != NULL) {
			curr = curr->next;
		}
		curr->next = new_node;
	}
}

// 反转链表的函数
Node *reverse_list(Node *head) {
    Node *prev = NULL;
    Node *current = head;
    Node *next = NULL;
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

// 判断链表是否为回文的函数
bool is_palindrome(Node *head) {
    if (head == NULL || head->next == NULL) {
        return true; // 空链表或单节点链表视为回文
    }

    Node *slow = head;
    Node *fast = head;

    // 快慢指针寻找中间节点
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    // 偶数长度从中间结点开始反转,奇数长度从中间结点的下一个结点开始反转
    Node *start_befor = (fast == NULL) ? slow : slow->next;   // 记录反转前后半部分链表的起点
    Node *start_after = reverse_list(start_befor);  // 记录反转后后半部分链表的起点,用于还原后半部分单链表
    Node *after_curr = start_after;     // after_curr用于遍历反转后的后半部分链表

    // 比较前半部分和反转后的后半部分
    Node *first_half = head;    // 前半部分结点的起点
    bool flag = true;
    while (after_curr != NULL) {
        if (first_half->data != after_curr->data) {
            flag = false;
            // 结束循环,然后还原单链表
            break;
        }
        first_half = first_half->next;
        after_curr = after_curr->next;
    }
    reverse_list(start_after);  // 再次反转后半部分以恢复原始顺序
    return flag;
}

int main(void) {
    Node *head = NULL;
    insert_tail(&head, 1);
    insert_tail(&head, 2);
    insert_tail(&head, 3);
    insert_tail(&head, 2);
    insert_tail(&head, 1);

    bool ret = is_palindrome(head);

    Node *head2 = NULL;
    insert_tail(&head2, 1);
    insert_tail(&head2, 2);
    insert_tail(&head2, 3);
    insert_tail(&head2, 4);
    insert_tail(&head2, 2);
    insert_tail(&head2, 1);
    bool ret2 = is_palindrome(head2);


    Node *head3 = NULL;
    insert_tail(&head3, 1);
    insert_tail(&head3, 2);
    insert_tail(&head3, 3);
    insert_tail(&head3, 3);
    insert_tail(&head3, 2);
    insert_tail(&head3, 1);
    bool ret3 = is_palindrome(head3);

	return 0;
}